package io.github.hadyang.leetcode.offer;

import org.junit.Test;

/** @author haoyang.shi */
public class CloneLink {
  public class RandomListNode {
    int label;
    RandomListNode next = null;
    RandomListNode random = null;

    RandomListNode(int label) {
      this.label = label;
    }
  }

  @Test
  public void test() {
    RandomListNode node1 = new RandomListNode(1);
    RandomListNode node2 = new RandomListNode(2);
    RandomListNode node3 = new RandomListNode(3);
    RandomListNode node4 = new RandomListNode(4);
    RandomListNode node5 = new RandomListNode(5);

    node1.next = node2;
    node2.next = node3;
    node3.next = node4;
    node4.next = node5;

    node1.random = node3;
    node2.random = node5;
    node4.random = node2;

    RandomListNode clone = Clone(node1);
    System.out.println(clone);
  }

  public RandomListNode Clone(RandomListNode pHead) {
    if (pHead == null) {
      return null;
    }

    RandomListNode cursor = pHead;
    while (cursor != null) {
      RandomListNode copyNode = new RandomListNode(cursor.label);

      RandomListNode nextNode = cursor.next;
      cursor.next = copyNode;
      copyNode.next = nextNode;

      cursor = nextNode;
    }

    cursor = pHead;
    while (cursor != null) {
      RandomListNode copyNode = cursor.next;

      if (cursor.random == null) {
        cursor = copyNode.next;
        continue;
      }

      copyNode.random = cursor.random.next;

      cursor = copyNode.next;
    }

    RandomListNode copyHead = pHead.next;
    cursor = pHead;
    while (cursor.next != null) {
      RandomListNode copyNode = cursor.next;
      cursor.next = copyNode.next;
      cursor = copyNode;
    }

    return copyHead;
  }
}
